{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pow(x, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: myPow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #Pow(x, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>实现&nbsp;<a href=\"https://www.cplusplus.com/reference/valarray/pow/\" target=\"_blank\">pow(<em>x</em>, <em>n</em>)</a>&nbsp;，即计算 <code>x</code> 的整数&nbsp;<code>n</code> 次幂函数（即，<code>x<sup>n</sup></code><sup><span style=\"font-size:10.8333px\"> </span></sup>）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 2.00000, n = 10\n",
    "<strong>输出：</strong>1024.00000\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 2.10000, n = 3\n",
    "<strong>输出：</strong>9.26100\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 2.00000, n = -2\n",
    "<strong>输出：</strong>0.25000\n",
    "<strong>解释：</strong>2<sup>-2</sup> = 1/2<sup>2</sup> = 1/4 = 0.25\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-100.0 &lt; x &lt; 100.0</code></li>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= n &lt;= 2<sup>31</sup>-1</code></li>\n",
    "\t<li><code>n</code>&nbsp;是一个整数</li>\n",
    "\t<li>要么 <code>x</code> 不为零，要么 <code>n &gt; 0</code> 。</li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= x<sup>n</sup> &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [powx-n](https://leetcode.cn/problems/powx-n/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [powx-n](https://leetcode.cn/problems/powx-n/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2.00000\\n10', '2.10000\\n3', '2.00000\\n-2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "\n",
    "        power = abs(n)\n",
    "        result = 1.0\n",
    "\n",
    "        while power > 0:\n",
    "            if power & 1:\n",
    "                result *= x\n",
    "            x *= x\n",
    "            power >>= 1\n",
    "\n",
    "        return result if n > 0 else 1 / result\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x, n):\n",
    "        \"\"\"\n",
    "        :type x: float\n",
    "        :type n: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        return pow(x,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: 'float', n: 'int') -> 'float':\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n > 0:\n",
    "            inverse = False\n",
    "        else:\n",
    "            inverse = True\n",
    "            n = -n\n",
    "            \n",
    "        ret = 1\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                if inverse:\n",
    "                    ret /= x\n",
    "                else:\n",
    "                    ret *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x, n):\n",
    "        \"\"\"\n",
    "        :type x: float\n",
    "        :type n: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        return x**n\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x, n):\n",
    "        \"\"\"\n",
    "        :type x: float\n",
    "        :type n: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n < 0:\n",
    "            x = 1/x\n",
    "            n = -n\n",
    "        res = 1\n",
    "        while n > 1:\n",
    "            if n % 2 :\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n //= 2\n",
    "        return res*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        res = 1.0\n",
    "        i = abs(n)\n",
    "        while i != 0:\n",
    "            if i % 2 != 0:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            i //= 2\n",
    "        return res if n >0 else 1/res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return x**n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n < 0:\n",
    "            x, n = 1/x, -n\n",
    "        result, current = 1, x\n",
    "        while n:\n",
    "            if n % 2:\n",
    "                result = result * current\n",
    "            current *= current\n",
    "            n //= 2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fastPow(self, x, n):\n",
    "        if n == 0:\n",
    "            return 1.0\n",
    "        half = self.fastPow(x, n // 2)\n",
    "        if not n % 2:\n",
    "            return half * half\n",
    "        else:\n",
    "            return half * half * x\n",
    "\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n < 0:\n",
    "            n = abs(n)\n",
    "            x = 1.0 / x\n",
    "        return self.fastPow(x, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x, n):\n",
    "        return x**n\n",
    "        if x==0:\n",
    "            return 0\n",
    "        if n==0:\n",
    "            return 1\n",
    "        res = self.POW(x, abs(n))\n",
    "        return res if n>0 else 1/res\n",
    "    \n",
    "    def POW(self, x, n):\n",
    "        if n==1:\n",
    "            return x\n",
    "        # if n==0:\n",
    "        #     return 1\n",
    "        count = 1\n",
    "        multi = x\n",
    "        while count+count < n:\n",
    "            count += count\n",
    "            multi *= multi\n",
    "        if count+count==n:\n",
    "            return multi*multi\n",
    "        else:\n",
    "            res = self.POW(x, n-count)\n",
    "            return multi*res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n==0:\n",
    "            return 1\n",
    "        p=1\n",
    "        b=n if n>0 else -n\n",
    "        while b>0:\n",
    "            if b&1==1:\n",
    "                p*=x\n",
    "            x=x*x\n",
    "            b>>=1\n",
    "        if n<0:\n",
    "            p=1/p\n",
    "        return p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n == 0: return 1\n",
    "        sign = (n >= 0)\n",
    "        if not sign: n = -n\n",
    "        \n",
    "        odd = []\n",
    "        while n > 1:\n",
    "            odd.append(n % 2)\n",
    "            n = n // 2\n",
    "        \n",
    "        s = x\n",
    "        for i in reversed(odd):\n",
    "            if i: s = s * s * x\n",
    "            else: s = s * s\n",
    "        \n",
    "        if sign: return s\n",
    "        else: return 1/s \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        #  time: O()\n",
    "        # space: O()\n",
    "        \n",
    "        if not n:\n",
    "            return 1.0\n",
    "        if x == 0:\n",
    "            return 0.0\n",
    "        if x ==  1:\n",
    "            return 1.0\n",
    "        if x == -1:\n",
    "            return -1.0 if n % 2 else 1.0\n",
    "        if n < 0:\n",
    "            x, n = 1/x, -n\n",
    "        res = 1\n",
    "        for _ in range(n):\n",
    "            res *= x\n",
    "            if abs(res) < 1e-10:\n",
    "                return res\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0:\n",
    "            return x\n",
    "        if n < 0:\n",
    "            x = 1 / x\n",
    "            n = -n\n",
    "        res = 1\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                res *= x\n",
    "            x = x * x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return pow(x, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def myPow(self, x: float, n: int) -> float:\r\n",
    "        def quickMul(N):\r\n",
    "            if N == 0:\r\n",
    "                return 1.0\r\n",
    "            y = quickMul(N // 2)\r\n",
    "            return y*y if N % 2 == 0 else y * y * x\r\n",
    "        \r\n",
    "        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from functools import lru_cache\n",
    "    @lru_cache(None)\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n == 0: return 1\n",
    "        if n == 1: return x\n",
    "        if n == 2: return x * x\n",
    "        if n == -1: return 1.0/x\n",
    "        if n == -2: return 1.0 / (x * x)\n",
    "        return self.myPow(x, n//2) * self.myPow(x, n - n//2) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from multiprocessing import Pool\n",
    "import os\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        \n",
    "        return math.pow(x,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from multiprocessing import Pool\n",
    "import os\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        \n",
    "        return math.pow(x,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        sign = n < 0\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        n = abs(n)\n",
    "        # def helper(num):\n",
    "        #     if num == 0:\n",
    "        #         return 1\n",
    "        #     tmp = helper(num>>1)\n",
    "        #     if num & 1:\n",
    "        #         return tmp * tmp * x\n",
    "        #     return tmp * tmp\n",
    "        # ans = helper(n)\n",
    "        contri = x\n",
    "        ans = 1\n",
    "        while n > 0:\n",
    "            if n & 1:\n",
    "                ans *= contri\n",
    "            contri *= contri\n",
    "            n >>= 1\n",
    "        return 1.0 / ans if sign else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0.0: return 0.0\n",
    "        res = 1\n",
    "        if n < 0: x, n = 1 / x, -n\n",
    "        while n:\n",
    "            if n & 1: res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return x**n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n==0:\n",
    "            return 1\n",
    "        if n<0:\n",
    "            return Solution().myPow(1/x,-n)\n",
    "        a = x\n",
    "        b = n//2\n",
    "        c = 1\n",
    "        while b:\n",
    "            a *= a\n",
    "            c *= 2\n",
    "            b //= 2\n",
    "        a *= Solution().myPow(x,n-c)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        def countPow(n):\n",
    "            if n ==  0:\n",
    "                return 1\n",
    "            else:\n",
    "                y = countPow(n // 2)\n",
    "                if n % 2 == 0:\n",
    "                    return y * y\n",
    "                else:\n",
    "                    return x * y * y\n",
    "\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        elif n > 0 :\n",
    "            return countPow(n)\n",
    "        else:\n",
    "            return 1 / countPow(-n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(maxsize=65536)\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n==0:\n",
    "            return 1\n",
    "        elif n<0:\n",
    "            return 1/self.myPow(x,-n)\n",
    "        elif n%2:\n",
    "            return x*self.myPow(x,n-1)\n",
    "        else:\n",
    "            temp=self.myPow(x,n/2)\n",
    "            return temp*temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        # 应该是快速幂，先试一下暴力\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n < 0:\n",
    "            n = -n \n",
    "            x = 1/x\n",
    "        \n",
    "        # 快速幂的本质是，乘完以后，还能够继续使用，比如快速的被二拆解\n",
    "        ## 所以，首先要看这个n能够被二拆解到多少\n",
    "        res = 1\n",
    "        temp = x\n",
    "        while n > 0:\n",
    "            # 说明此时能够留1\n",
    "            if n % 2 == 1:\n",
    "                # print(1, n, temp)\n",
    "                res *= temp\n",
    "            temp *= temp\n",
    "            # res *= x\n",
    "            n //= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0.0: return 0.0\n",
    "        res = 1\n",
    "        if n < 0: x, n = 1 / x, -n\n",
    "        while n:\n",
    "            if n & 1: res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        def quick(N):\n",
    "            if N == 0:\n",
    "                return 1.0\n",
    "            y = quick(N//2)\n",
    "            return y*y if N%2==0 else y*y*x\n",
    "        return quick(n) if n>=0 else 1.0 / quick(-n)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
